package com.cn.codebrush.数组;

public class No75颜色分类 {
    public static void main(String[] args) {

    }

    /**
     * 计数排序
     * @param nums
     */
    public void sortColors(int[] nums) {
        int maxVal = nums[0];
        for(int val:nums){
            if(val > maxVal){
                maxVal = val;
            }
        }
        int[] newNums = new int[maxVal+1];
        for(int val:nums){
            newNums[val]++;
        }

        int index = 0;
        for(int j=0;j<newNums.length;j++){
            while(newNums[j] > 0){
                nums[index++] = j;
                newNums[j]--;
            }
        }

    }


    /**
     * 快速排序
     * 利用分治思想，分为左右两个部分
     * 选择最低位的数字作为基准，最右边开始扫描，一直遇到小于基准的进行交换，再从最左边开始扫描，遇到大于基准的进行交换
     * 扫描一遍完成之后，基准左边小于基准，基准右边全是大于基准
     * 然后重复上面的过程，直到有序
     * @param nums
     */
    public void sortColors2(int[] nums) {
        int n = nums.length;
        sortColorsQuick(nums,0,n-1);
    }
    public void sortColorsQuick(int[] nums,int low,int high) {
        if (low < high){
            int index = sortColorsQuickHelper(nums,low,high);
            sortColorsQuick(nums,low,index-1);
            sortColorsQuick(nums,index+1,high);
        }
    }
    public int sortColorsQuickHelper(int[] nums,int low,int high) {
        int temp = nums[low];
        while (low < high){
            while (low <high && nums[high] >= temp){
                high--;
            }
            nums[low] = nums[high];
            while (low < high && nums[low] <= temp){
                low++;
            }
            nums[high] = nums[low];
        }
        nums[low] = temp;
        return low;
    }



    /**
     * 冒泡排序
     * @param nums
     */
    public void sortColors1(int[] nums) {
        int n = nums.length;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(nums[i] > nums[j]){
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
            }
        }
    }
}
